#  有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
#  省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
#
#  给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而
# isConnected[i][j] = 0 表示二者不直接相连。
#
#  返回矩阵中 省份 的数量。
#
#  示例 1：
# 输入：isConnected = [
# [1,1,0],
# [1,1,0],
# [0,0,1]]
# 输出：2
#
#  示例 2：
# 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
# 输出：3
from typing import List


class Solution:
    def findCircleNum2(self, isConnected: List[List[int]]) -> int:
        class UnionFindSet:
            def __init__(self, nodeSize: int):
                self.parents = list(range(nodeSize))
                self.ranks = [0] * nodeSize
                self.counts = nodeSize

            def find(self, node: int) -> int:
                # 迭代写法
                while node != self.parents[node]:
                    self.parents[node] = self.parents[self.parents[node]]
                    node = self.parents[node]
                return node
                # 递归写法
                # if self.parents[node] != node:
                #     self.parents[node] = self.find(self.parents[node])
                # return self.parents[node]

            def union(self, node1: int, node2: int) -> None:
                # self.parents[self.find(node1)] = self.find(node2)  # 不考虑秩的大小就直接进行合并
                p1, p2 = self.find(node1), self.find(node2)
                if p1 != p2:
                    self.counts -= 1
                    if self.ranks[p1] > self.ranks[p2]:
                        self.parents[p2] = p1
                    elif self.ranks[p1] < self.ranks[p2]:
                        self.parents[p1] = p2
                    else:
                        self.parents[p2] = p1
                        self.ranks[p1] += 1

        n = len(isConnected)
        uf = UnionFindSet(n)
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    uf.union(i, j)
        # print(uf.parents)
        return sum(uf.parents[i] == i for i in range(n))
        # return uf.counts

    def findCircleNum1(self, isConnected: List[List[int]]) -> int:
        """
        解法一：dfs
        :param isConnected:
        :return:
        """
        n = len(isConnected)
        visited = [False] * n
        counts = 0

        def dfs(start: int) -> None:
            visited[start] = True
            for neighbour in range(n):
                if not visited[neighbour] and isConnected[start][neighbour] == 1:
                    dfs(neighbour)

        while False in visited:
            counts += 1
            for i in range(n):
                if not visited[i]:
                    dfs(i)
                    break
        return counts

    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        return self.findCircleNum2(isConnected)


if __name__ == "__main__":
    isConnected = [
        [1, 1, 0],
        [1, 1, 0],
        [0, 0, 1]]
    isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
    isConnected = [[1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
                   [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                   [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
                   [0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
                   [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
                   [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0],
                   [0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
                   [1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0],
                   [0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1],
                   [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
                   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
                   [0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0],
                   [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]]
    print(Solution().findCircleNum(isConnected))
